FIG. 1 illustrates a prior art graphics system 100 having a central processing unit (CPU) 105 and a graphics processing unit (GPU) 110. GPU 110 has graphics hardware, such as a graphics pipeline 115. A memory 130 stores programs that execute on CPU 105. A graphics application 135 generates graphical commands. A graphics driver 140 converts the abstract graphics commands into a format the graphics hardware of GPU 110 can utilize to render an image. Thus, the graphics driver 140 can be understood as receiving inputs from the graphics application 135 and generating outputs for GPU 110.
The sets of inputs and outputs of graphics driver 140 will have associated states. Consequently, the function of graphics driver 140 can also be understood in terms of performing a mapping between a set of input states and a set of output states 118 received by GPU 110. The input state is also sometimes known as the “user state.” The output state is sometimes known as a “hardware state” because the output state is in a format that graphics hardware can utilize. Examples of user state include a fragment program, a depth function, and a stencil testing function. As the user state associated with the graphics application evolves the output state generated by the graphics driver will also change. The output of the graphics driver includes, for example, graphics commands and other information sent to the GPU. Examples of output state include a micro-coded program executed on the graphics hardware or a vertex array state (e.g., pointers or formats).
As an input (user state) evolves an appropriate output state for the graphics hardware needs to be determined by the graphics driver. There can be a significant computational cost associated with calculating a transformation from an input state to an output state. Consequently, in the prior art output states were sometimes cached using an output state cache 145 to store a representation of output state that could be reused. As an example, in the prior art a graphics application could render a scene in a particular way, such as to render a state of character A and then to render a state of character B. For some types of applications the same graphics operations occur repetitively, such as repetitively within a scene or between frames. As a result, graphics driver 140 would use an output state cache 145 to reuse a transformation that was performed repetitively.
FIG. 2 illustrates in more detail a sequence of steps performed by graphics driver 140 to utilize output state cache 145. Output state cache 145 stores a full set of recently used output states constrained by some maximum cache limit and/or a cache policy. User input state values 205 were hashed to compute indexing keys 210 into the output state cache 145. That is, each output state was separately indexed by a key to a respective input state value. A lookup key operation 215 could then be subsequently used to map a user input state to an output state.
A drawback of using output state cache 145 is that it becomes inefficient as the number of states increases. Performing a hash operation on a set of input states to compute keys and perform a lookup becomes computationally expensive when the number of input states increases. In particular, computing the hash key is computationally expensive. As a consequence, the system of FIG. 1 has performance problems when the number of input states increases beyond a certain number.
In light of the problems described above, the apparatus, system, method, and computer readable medium of the present invention was developed.